/**
 * @param {number} n
 * @param {number[][]} relations
 * @param {number[]} time
 * @return {number}
 */
var minimumTime = function (n, relations, time) {
  const map = new Map();
  const memo = new Array(n + 1).fill(0); // 存储计算过的最小时间，初始化为 0
  const set = new Set();
  relations.forEach((e) => {
    map.set(e[1], map.has(e[1]) ? map.get(e[1]).concat(e[0]) : [e[0]]);
    set.add(e[0]);
  });
  const root = [];
  for (let i = 1; i <= n; i++) {
    if (!set.has(i)) root.push(i);
  }
  return Math.max(...root.map((val) => findMinTimeDP(val, time, map, memo)));
};

function findMinTimeDP(val, time, map, memo) {
  console.log(memo);

  return memo[val] > 0
    ? memo[val]
    : memo[val] = time[val - 1] +
        (map.has(val)
          ? Math.max(...map.get(val).map((v) => findMinTimeDP(v, time, map, memo)))
          : 0);
}
const n = 9,
  relations = [[2,7],[2,6],[3,6],[4,6],[7,6],[2,1],[3,1],[4,1],[6,1],[7,1],[3,8],[5,8],[7,8],[1,9],[2,9],[6,9],[7,9]]
  ,
  time = [9,5,9,5,8,7,7,8,4];
console.log(minimumTime(n, relations, time));
// 该题目用到了森林，树，动态规划的知识，并且需要用到动态规划的记忆存储，较为综合，是个好题
